package codetop.microsoft.T53;

/**
 * @Author: 18362
 * @Create: 2022-08-13 15:51:36 星期六
 */
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        System.arraycopy(nums, 0, dp, 0, nums.length);
        int maxSum = dp[0];
        for (int i=1; i<nums.length; ++i) {
            dp[i] = Math.max(dp[i], dp[i-1] + nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}